//
// Created by lanlu on 2025/8/14.
//

// 拓扑排序
#include <queue>
#include <vector>
#include <iostream>
using namespace std;

vector<int> topologicalSort(int n, vector<vector<int>>& graph)
{
    // 创建入度数组
    vector<int> inDegree(n, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j : graph[i])
        {
            // i->j 所以j的入度+1
            inDegree[j]++;
        }
    }

    // 创建队列
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        if (inDegree[i] == 0)
        {
            // 入度为0的顶点入队
            q.push(i);
        }
    }

    // 记录排序结果
    vector<int> res;
    while (!q.empty())
    {
        // 取出队首的顶点
        int cur = q.front();
        q.pop();
        res.push_back(cur);

        // 将相邻顶点的入度-1
        for (int v: graph[cur])
        {
            inDegree[v]--;
            if (inDegree[v] == 0)
            {
                q.push(v);
            }
        }
    }

    if (res.size() != n)
    {
        return  {};
    }
    return res;
}

int main()
{
    // A B C D
    // 0 1 2 3
    int n = 4;
    vector<vector<int>> graph = {
        {1,2}, // A->B  A->C
        {3}, // B->D
        {3}, // C->D
        {}
    };

    vector<int> res = topologicalSort(n,  graph);
    for (int i : res)
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}